// Copyright (C) 2024 EA group inc.
// Author: Jeff.li lijippy@163.com
// All rights reserved.
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU Affero General Public License as published
// by the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU Affero General Public License for more details.
//
// You should have received a copy of the GNU Affero General Public License
// along with this program.  If not, see <https://www.gnu.org/licenses/>.
//
//
// -----------------------------------------------------------------------------
// type_traits.h
// -----------------------------------------------------------------------------
//
// This file contains C++11-compatible versions of standard <type_traits> API
// functions for determining the characteristics of types. Such traits can
// support type inference, classification, and transformation, as well as
// make it easier to write templates based on generic type behavior.
//
// See https://en.cppreference.com/w/cpp/header/type_traits
//
// WARNING: use of many of the constructs in this header will count as "complex
// template metaprogramming", so before proceeding, please carefully consider
// https://google.github.io/styleguide/cppguide.html#Template_metaprogramming
//
// WARNING: using template metaprogramming to detect or depend on API
// features is brittle and not guaranteed. Neither the standard library nor
// Turbo provides any guarantee that APIs are stable in the face of template
// metaprogramming. Use with caution.
#ifndef TURBO_META_TYPE_TRAITS_H_
#define TURBO_META_TYPE_TRAITS_H_

#include <cstddef>
#include <functional>
#include <string>
#include <type_traits>
#include <vector>
#include <list>
#include <deque>
#include <set>
#include <unordered_set>
#include <turbo/base/macros.h>

#ifdef __cpp_lib_span
#include <span>  // NOLINT(build/c++20)
#endif

#include <string_view>

// Defines the default alignment. `__STDCPP_DEFAULT_NEW_ALIGNMENT__` is a C++17
// feature.
#if defined(__STDCPP_DEFAULT_NEW_ALIGNMENT__)
#define TURBO_INTERNAL_DEFAULT_NEW_ALIGNMENT __STDCPP_DEFAULT_NEW_ALIGNMENT__
#else  // defined(__STDCPP_DEFAULT_NEW_ALIGNMENT__)
#define TURBO_INTERNAL_DEFAULT_NEW_ALIGNMENT alignof(std::max_align_t)
#endif  // defined(__STDCPP_DEFAULT_NEW_ALIGNMENT__)

namespace turbo {

    namespace type_traits_internal {

        template<typename... Ts>
        struct VoidTImpl {
            using type = void;
        };

        ////////////////////////////////
        // Library Fundamentals V2 TS //
        ////////////////////////////////

        // NOTE: The `is_detected` family of templates here differ from the library
        // fundamentals specification in that for library fundamentals, `Op<Args...>` is
        // evaluated as soon as the type `is_detected<Op, Args...>` undergoes
        // substitution, regardless of whether or not the `::value` is accessed. That
        // is inconsistent with all other standard traits and prevents lazy evaluation
        // in larger contexts (such as if the `is_detected` check is a trailing argument
        // of a `conjunction`. This implementation opts to instead be lazy in the same
        // way that the standard traits are (this "defect" of the detection idiom
        // specifications has been reported).

        template<class Enabler, template<class...> class Op, class... Args>
        struct is_detected_impl {
            using type = std::false_type;
        };

        template<template<class...> class Op, class... Args>
        struct is_detected_impl<typename VoidTImpl<Op<Args...>>::type, Op, Args...> {
            using type = std::true_type;
        };

        template<template<class...> class Op, class... Args>
        struct is_detected : is_detected_impl<void, Op, Args...>::type {
        };

        template<class Enabler, class To, template<class...> class Op, class... Args>
        struct is_detected_convertible_impl {
            using type = std::false_type;
        };

        template<class To, template<class...> class Op, class... Args>
        struct is_detected_convertible_impl<
                typename std::enable_if<std::is_convertible<Op<Args...>, To>::value>::type,
                To, Op, Args...> {
            using type = std::true_type;
        };

        template<class To, template<class...> class Op, class... Args>
        struct is_detected_convertible
                : is_detected_convertible_impl<void, To, Op, Args...>::type {
        };

    }  // namespace type_traits_internal

#if defined(__cpp_lib_remove_cvref) && __cpp_lib_remove_cvref >= 201711L
    template <typename T>
    using remove_cvref = std::remove_cvref<T>;

    template <typename T>
    using remove_cvref_t = typename std::remove_cvref<T>::type;
#else
    // remove_cvref()
    //
    // C++11 compatible implementation of std::remove_cvref which was added in
    // C++20.
    template<typename T>
    struct remove_cvref {
        using type =
                typename std::remove_cv<typename std::remove_reference<T>::type>::type;
    };

    template<typename T>
    using remove_cvref_t = typename remove_cvref<T>::type;
#endif

    namespace type_traits_internal {

#if (defined(__cpp_lib_is_invocable) && __cpp_lib_is_invocable >= 201703L) || \
    (defined(_MSVC_LANG) && _MSVC_LANG >= 201703L)
// std::result_of is deprecated (C++17) or removed (C++20)
        template<typename>
        struct result_of;
        template<typename F, typename... Args>
        struct result_of<F(Args...)> : std::invoke_result<F, Args...> {
        };
#else
        template <typename F>
        using result_of = std::result_of<F>;
#endif

    }  // namespace type_traits_internal

    template<typename F>
    using result_of_t = typename type_traits_internal::result_of<F>::type;

    template<typename ReturnType, typename F, typename... Args>
    struct is_result_same
            : public std::is_same<ReturnType, result_of_t<F(Args...)>> {};

    template<typename F, typename... Args>
    struct is_result_void : public is_result_same<void, F, Args...> {};

    // Whether a callable returns int.
    template<typename F, typename... Args>
    struct is_result_int : public is_result_same<int, F, Args...> {};

    // Whether a callable returns int.
    template<typename R, typename F, typename... Args>
    struct is_result_type : public is_result_same<R, F, Args...> {};

    namespace type_traits_internal {
// In MSVC we can't probe std::hash or stdext::hash because it triggers a
// static_assert instead of failing substitution. Libc++ prior to 4.0
// also used a static_assert.
//
#if defined(_MSC_VER) || (defined(_LIBCPP_VERSION) && \
                          _LIBCPP_VERSION < 4000 && _LIBCPP_STD_VER > 11)
#define TURBO_META_INTERNAL_STD_HASH_SFINAE_FRIENDLY_ 0
#else
#define TURBO_META_INTERNAL_STD_HASH_SFINAE_FRIENDLY_ 1
#endif

#if !TURBO_META_INTERNAL_STD_HASH_SFINAE_FRIENDLY_
        template <typename Key, typename = size_t>
        struct IsHashable : std::true_type {};
#else   // TURBO_META_INTERNAL_STD_HASH_SFINAE_FRIENDLY_
        template<typename Key, typename = void>
        struct IsHashable : std::false_type {
        };

        template<typename Key>
        struct IsHashable<
                Key,
                std::enable_if_t<std::is_convertible<
                        decltype(std::declval<std::hash<Key> &>()(std::declval<Key const &>())),
                        std::size_t>::value>> : std::true_type {
        };
#endif  // !TURBO_META_INTERNAL_STD_HASH_SFINAE_FRIENDLY_

        struct AssertHashEnabledHelper {
        private:
            static void Sink(...) {}

            struct NAT {
            };

            template<class Key>
            static auto GetReturnType(int)
            -> decltype(std::declval<std::hash<Key>>()(std::declval<Key const &>()));

            template<class Key>
            static NAT GetReturnType(...);

            template<class Key>
            static std::nullptr_t DoIt() {
                static_assert(IsHashable<Key>::value,
                              "std::hash<Key> does not provide a call operator");
                static_assert(
                        std::is_default_constructible<std::hash<Key>>::value,
                        "std::hash<Key> must be default constructible when it is enabled");
                static_assert(
                        std::is_copy_constructible<std::hash<Key>>::value,
                        "std::hash<Key> must be copy constructible when it is enabled");
                static_assert(std::is_copy_assignable<std::hash<Key>>::value,
                              "std::hash<Key> must be copy assignable when it is enabled");
                // is_destructible is unchecked as it's implied by each of the
                // is_constructible checks.
                using ReturnType = decltype(GetReturnType<Key>(0));
                static_assert(std::is_same<ReturnType, NAT>::value ||
                              std::is_same<ReturnType, size_t>::value,
                              "std::hash<Key> must return size_t");
                return nullptr;
            }

            template<class... Ts>
            friend void AssertHashEnabled();
        };

        template<class... Ts>
        inline void AssertHashEnabled() {
            using Helper = AssertHashEnabledHelper;
            Helper::Sink(Helper::DoIt<Ts>()...);
        }

    }  // namespace type_traits_internal

// An internal namespace that is required to implement the C++17 swap traits.
// It is not further nested in type_traits_internal to avoid long symbol names.
    namespace swap_internal {

// Necessary for the traits.
        using std::swap;

// This declaration prevents global `swap` and `turbo::swap` overloads from being
// considered unless ADL picks them up.
        void swap();

        template<class T>
        using IsSwappableImpl = decltype(swap(std::declval<T &>(), std::declval<T &>()));

// NOTE: This dance with the default template parameter is for MSVC.
        template<class T,
                class IsNoexcept = std::integral_constant<
                        bool, noexcept(swap(std::declval<T &>(), std::declval<T &>()))>>
        using IsNothrowSwappableImpl = typename std::enable_if<IsNoexcept::value>::type;

// IsSwappable
//
// Determines whether the standard swap idiom is a valid expression for
// arguments of type `T`.
        template<class T>
        struct IsSwappable
                : turbo::type_traits_internal::is_detected<IsSwappableImpl, T> {
        };

// IsNothrowSwappable
//
// Determines whether the standard swap idiom is a valid expression for
// arguments of type `T` and is noexcept.
        template<class T>
        struct IsNothrowSwappable
                : turbo::type_traits_internal::is_detected<IsNothrowSwappableImpl, T> {
        };

        // Swap()
        //
        // Performs the swap idiom from a namespace where valid candidates may only be
        // found in `std` or via ADL.
        template<class T, std::enable_if_t<IsSwappable<T>::value, int> = 0>
        void Swap(T &lhs, T &rhs) noexcept(IsNothrowSwappable<T>::value) {
            swap(lhs, rhs);
        }

        // StdSwapIsUnconstrained
        //
        // Some standard library implementations are broken in that they do not
        // constrain `std::swap`. This will effectively tell us if we are dealing with
        // one of those implementations.
        using StdSwapIsUnconstrained = IsSwappable<void()>;

    }  // namespace swap_internal

    namespace type_traits_internal {

        // Make the swap-related traits/function accessible from this namespace.
        using swap_internal::IsNothrowSwappable;
        using swap_internal::IsSwappable;
        using swap_internal::StdSwapIsUnconstrained;
        using swap_internal::Swap;

    }  // namespace type_traits_internal

// turbo::is_trivially_relocatable<T>
//
// Detects whether a type is known to be "trivially relocatable" -- meaning it
// can be relocated from one place to another as if by memcpy/memmove.
// This implies that its object representation doesn't depend on its address,
// and also none of its special member functions do anything strange.
//
// This trait is conservative. If it's true then the type is definitely
// trivially relocatable, but if it's false then the type may or may not be. For
// example, std::vector<int> is trivially relocatable on every known STL
// implementation, but turbo::is_trivially_relocatable<std::vector<int>> remains
// false.
//
// Example:
//
// if constexpr (turbo::is_trivially_relocatable<T>::value) {
//   memcpy(new_location, old_location, sizeof(T));
// } else {
//   new(new_location) T(std::move(*old_location));
//   old_location->~T();
// }
//
// Upstream documentation:
//
// https://clang.llvm.org/docs/LanguageExtensions.html#:~:text=__is_trivially_relocatable

// If the compiler offers a builtin that tells us the answer, we can use that.
// This covers all of the cases in the fallback below, plus types that opt in
// using e.g. [[clang::trivial_abi]].
//
// Clang on Windows has the builtin, but it falsely claims types with a
// user-provided destructor are trivial (http://b/275003464). So we opt out
// there.
//
// TODO(b/275003464): remove the opt-out once the bug is fixed.
//
// Starting with Xcode 15, the Apple compiler will falsely say a type
// with a user-provided move constructor is trivially relocatable
// (b/324278148). We will opt out without a version check, due to
// the fluidity of Apple versions.
//
// TODO(b/324278148): If all versions we use have the bug fixed, then
// remove the condition.
//
// Clang on all platforms fails to detect that a type with a user-provided
// move-assignment operator is not trivially relocatable. So in fact we
// opt out of Clang altogether, for now.
//
// TODO(b/325479096): Remove the opt-out once Clang's behavior is fixed.
//
// According to https://github.com/abseil/abseil-cpp/issues/1479, this does not
// work with NVCC either.
#if TURBO_HAVE_BUILTIN(__is_trivially_relocatable) && \
    (defined(__cpp_impl_trivially_relocatable) || \
     (!defined(__clang__) && !defined(__APPLE__) && !defined(__NVCC__)))
    template <class T>
    struct is_trivially_relocatable
        : std::integral_constant<bool, __is_trivially_relocatable(T)> {};
#else
// Otherwise we use a fallback that detects only those types we can feasibly
// detect. Any type that is trivially copyable is by definition trivially
// relocatable.
    template<class T>
    struct is_trivially_relocatable : std::is_trivially_copyable<T> {
    };
#endif

// turbo::is_constant_evaluated()
//
// Detects whether the function call occurs within a constant-evaluated context.
// Returns true if the evaluation of the call occurs within the evaluation of an
// expression or conversion that is manifestly constant-evaluated; otherwise
// returns false.
//
// This function is implemented in terms of `std::is_constant_evaluated` for
// c++20 and up. For older c++ versions, the function is implemented in terms
// of `__builtin_is_constant_evaluated` if available, otherwise the function
// will fail to compile.
//
// Applications can inspect `TURBO_HAVE_CONSTANT_EVALUATED` at compile time
// to check if this function is supported.
//
// Example:
//
// constexpr MyClass::MyClass(int param) {
// #ifdef TURBO_HAVE_CONSTANT_EVALUATED
//   if (!turbo::is_constant_evaluated()) {
//     TURBO_LOG(INFO) << "MyClass(" << param << ")";
//   }
// #endif  // TURBO_HAVE_CONSTANT_EVALUATED
// }
//
// Upstream documentation:
//
// http://en.cppreference.com/w/cpp/types/is_constant_evaluated
// http://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html#:~:text=__builtin_is_constant_evaluated
//
#if defined(TURBO_HAVE_CONSTANT_EVALUATED)
    constexpr bool is_constant_evaluated() noexcept {
#ifdef __cpp_lib_is_constant_evaluated
      return std::is_constant_evaluated();
#elif TURBO_HAVE_BUILTIN(__builtin_is_constant_evaluated)
      return __builtin_is_constant_evaluated();
#endif
    }
#endif  // TURBO_HAVE_CONSTANT_EVALUATED

    namespace type_traits_internal {

        // Detects if a class's definition has declared itself to be an owner by
        // declaring
        //   using turbo_internal_is_view = std::true_type;
        // as a member.
        // Types that don't want either must either omit this declaration entirely, or
        // (if e.g. inheriting from a base class) define the member to something that
        // isn't a Boolean trait class, such as `void`.
        // Do not specialize or use this directly. It's an implementation detail.
        template<typename T, typename = void>
        struct IsOwnerImpl : std::false_type {
            static_assert(std::is_same<T, turbo::remove_cvref_t<T>>::value,
                          "type must lack qualifiers");
        };

        template<typename T>
        struct IsOwnerImpl<
                T,
                std::enable_if_t<std::is_class<typename T::turbo_internal_is_view>::value>>
                : std::negation<typename T::turbo_internal_is_view> {
        };

        // A trait to determine whether a type is an owner.
        // Do *not* depend on the correctness of this trait for correct code behavior.
        // It is only a safety feature and its value may change in the future.
        // Do not specialize this; instead, define the member trait inside your type so
        // that it can be auto-detected, and to prevent ODR violations.
        // If it ever becomes possible to detect [[gsl::Owner]], we should leverage it:
        // https://wg21.link/p1179
        template<typename T>
        struct IsOwner : IsOwnerImpl<T> {
        };

        template<typename T, typename Traits, typename Alloc>
        struct IsOwner<std::basic_string<T, Traits, Alloc>> : std::true_type {
        };

        template<typename T, typename Alloc>
        struct IsOwner<std::vector<T, Alloc>> : std::true_type {
        };

        // Detects if a class's definition has declared itself to be a view by declaring
        //   using turbo_internal_is_view = std::true_type;
        // as a member.
        // Do not specialize or use this directly.
        template<typename T, typename = void>
        struct IsViewImpl : std::false_type {
            static_assert(std::is_same<T, turbo::remove_cvref_t<T>>::value,
                          "type must lack qualifiers");
        };

        template<typename T>
        struct IsViewImpl<
                T,
                std::enable_if_t<std::is_class<typename T::turbo_internal_is_view>::value>>
                : T::turbo_internal_is_view {
        };

        // A trait to determine whether a type is a view.
        // Do *not* depend on the correctness of this trait for correct code behavior.
        // It is only a safety feature, and its value may change in the future.
        // Do not specialize this trait. Instead, define the member
        //   using turbo_internal_is_view = std::true_type;
        // in your class to allow its detection while preventing ODR violations.
        // If it ever becomes possible to detect [[gsl::Pointer]], we should leverage
        // it: https://wg21.link/p1179
        template<typename T>
        struct IsView : std::integral_constant<bool, std::is_pointer<T>::value ||
                                                     IsViewImpl<T>::value> {
        };

        template<typename Char, typename Traits>
        struct IsView<std::basic_string_view<Char, Traits>> : std::true_type {
        };

#ifdef __cpp_lib_span
        template <typename T>
        struct IsView<std::span<T>> : std::true_type {};
#endif

        // Determines whether the assignment of the given types is lifetime-bound.
        // Do *not* depend on the correctness of this trait for correct code behavior.
        // It is only a safety feature and its value may change in the future.
        // If it ever becomes possible to detect [[clang::lifetimebound]] directly,
        // we should change the implementation to leverage that.
        // Until then, we consider an assignment from an "owner" (such as std::string)
        // to a "view" (such as std::string_view) to be a lifetime-bound assignment.
        template<typename T, typename U>
        using IsLifetimeBoundAssignment =
                std::integral_constant<bool, IsView<turbo::remove_cvref_t<T>>::value &&
                                             IsOwner<turbo::remove_cvref_t<U>>::value>;

    }  // namespace type_traits_internal

    template<typename X, typename Y>
    struct is_same_reference
            : std::is_same<typename std::remove_cv<
                    typename std::remove_reference<X>::type>::type,
                    typename std::remove_cv<
                            typename std::remove_reference<Y>::type>::type> {
    };

    template<typename X, typename Y>
    using requires_convertible = typename std::enable_if<
            std::disjunction<std::is_convertible<X, Y>,
                    is_same_reference<X, Y>>::value,
            int>::type;

    template<typename T, typename = void>
    struct is_container : std::false_type {
        using value_type = void;
    };

    template<typename T>
    struct is_container<T,
            std::void_t<decltype(std::declval<T>().begin()),
                    decltype(std::declval<T>().end()),
                    typename T::value_type
            >> : std::true_type // will  be enabled for iterable objects
    {
        using value_type = typename T::value_type;
    };

    template<typename T, typename V>
    struct is_container_of {
        static constexpr bool value =
                is_container<T>::value & std::is_same<V, typename is_container<T>::value_type>::value;
        using value_type = V;
    };

    template<typename T, typename V>
    struct is_convertible_container {
        static constexpr bool value = is_container<T>::value &
                                      std::disjunction<
                                              std::is_convertible<typename is_container<T>::value_type, V>,
                                              is_same_reference<typename is_container<T>::value_type, V>
                                      >::value;
    };

    template<typename T>
    struct sequence_container : public std::false_type {
        using value_type = void;
    };

    template<typename T>
    struct sequence_container<std::initializer_list<T>> : public std::true_type {
        using value_type = T;
    };

    template<typename T>
    struct sequence_container<std::vector<T>> : public std::true_type {
        using value_type = T;
    };

    template<typename T>
    struct sequence_container<std::list<T>> : public std::true_type {
        using value_type = T;
    };

    template<typename T>
    struct sequence_container<std::deque<T>> : public std::true_type {
        using value_type = T;
    };

    template<typename T>
    struct sequence_container<std::set<T>> : public std::true_type {
        using value_type = T;
    };

    template<typename T>
    struct sequence_container<std::unordered_set<T>> : public std::true_type {
        using value_type = T;
    };

}  // namespace turbo

#endif  // TURBO_META_TYPE_TRAITS_H_
